בנם של מריה וניקולאי. נולד ביום י"ג בשבט תשמ"ד (17.1.1984) בחצי האי קרים שבאוקראינה. אח ליוג'ין וטטיאנה.

אנדריי גדל והתחנך בכפר קטן בדרום אוקראינה. למד בבתי ספר באזור מגוריו.

בנעוריו גילה שסבתו יהודייה וניצולת שואה. הגילוי עורר בו מחשבות והרהורים והשפיע עליו, ובעקבות זאת חלם לעלות ארצה.

בקשתו לעלות לישראל נדחתה בגלל שירות החובה בצבא אוקראינה. על כן בסיום לימודיו התגייס לצבא אוקראינה ושובץ בגדוד מבצעי בחטיבת משמר הנשיא, שמטרתו שמירת הסדר ברחובות ופיזור הפגנות מיוחדות. השירות היה מאתגר מאוד וכלל סדר יום נוקשה ומשמעת ברזל. לכל אורכו לא זכה אנדריי לחופשות בבית ולמפגשים עם משפחתו. לדבריו, התנאים האלה פיתחו בו תכונות מסוימות: "אתה לומד להסתדר לבד. נכנס ילד קטן, ואחרי שנה וחצי של ניתוק מהחיים שהכרת, אתה חייב לשרוד, לצאת משם גבר".

בהיותו בן עשרים, בשנת 2004, שלושה חודשים לאחר שהשתחרר מצבא אוקראינה, עלה ארצה בגפו, מתוך רצון לנסות חיים אחרים, נוחים ושקטים יותר וללמוד במוסד אקדמי איכותי. הוא השתקע בבאר שבע והחל ללמוד.

כעבור כמה שנים עזב את לימודיו והתגייס לצה"ל, במעמד חייל בודד. הוא שובץ בחיל החימוש (לימים חיל הטכנולוגיה והאחזקה). לאחר זמן יצא לקורס קציני חימוש, ואחריו שימש קצין חימוש בבסיס של חיל התותחנים ואף המשיך לשירות קבע. בתקופה זו החל לחוש חלק בלתי נפרד מהחברה הישראלית.

בספטמבר 2011 התראיין לכתבה בשבועון הצה"לי "במחנה" שעסקה בחיילים שהתגייסו לצבא זר לפני שהתגייסו לצה"ל. הכתבה זמינה לצפייה באתר Mako ובה תיאר את פליאתו ואת שביעות רצונו מהרווחה שזכה לה בצה"ל לעומת צבא אוקראינה – היציאות התכופות הביתה, הדאגה לו כחייל בודד והאכפתיות שחש בה מצד היחידה ומהסובבים אותו.

בתום שמונה שנות שירות בצה"ל השתחרר. מאחר שרצה להמשיך לשרת ולתרום למדינה, בחר להתגייס למשטרת ישראל. ואכן, ביום 1.12.2016 התגייס והחל את ההכשרה. את כל שירותו עשה במחוז דרום. בשנותיו הראשונות בתפקיד סַייר שירת בתחנת באר שבע, ולאחר שעבר קורס קציני משטרה, הוצב כקצין סיור בתחנת "עיירות" ביחידת "יואב" במרחב נגב. אנדריי חש גאווה ומימוש עצמי בהיותו קצין, והיה מפקד מוערך. פקודיו ראו בו דמות אב, והוא לימד אותם בין היתר לא לוותר לעצמם. "תזכרו שאתם לא חד-פעמיים", נהג לומר להם.

במסגרת שירותו למד לתואר ראשון בפקולטה למשפטים במכון לקרימינולוגיה באוניברסיטה העברית בירושלים. לאחר מכן התחיל בלימודי מוסמך תוכנית פו"ם (פיקוד ומטה) בבית הספר למדע המדינה באוניברסיטת חיפה.

אנדריי אהב ספורט ובשעות הפנאי הקפיד להתאמן ולשמור על כושר גופני גבוה.

בחור כארז, כדברי כל חבריו, מוכשר, נעים הליכות עם חיוך תמידי, כבש את ליבם של כל מי שנקרו בדרכו. בורך ברוחב לב ובנתינה ועשה הכול בחיוך וברוח טובה. ערכים של ציונות, אהבת הארץ וכבוד האדם היו נר לרגליו. בהתמדה ובנחישות השיג את מטרותיו ולא ויתר גם אם נאלץ להתמודד עם קשיים בדרך.

בשבת כ"ב בתשרי, שמחת תורה תשפ"ד, 7 באוקטובר 2023, בשעה שש וחצי בבוקר, פתח ארגון הטרור חמאס במתקפת פתע על ישראל. בחסות ירי מסיבי של טילים ורקטות מרצועת עזה לאזורים נרחבים בארץ חדרו אלפי מחבלים – יבשתית, ימית ואווירית, והחלו במתקפה רצחנית על יישובי עוטף עזה ועל שדרות, אופקים ונתיבות, על מְבַלי מסיבות טבע סמוך לקיבוצים רעים ונירים, על בסיסי צה"ל ועל העוברים בדרכים באזור. המחבלים רצחו כשמונה-מאות אזרחים בבתיהם, במכוניותיהם, אחרי שביצעו בהם פשעים כבדים. חטפו לרצועת עזה מאות ישראלים והחריבו, בזזו והעלו באש בתים ורכוש. מאות חיילים, שוטרים, אנשי כוחות הביטחון וחברי כיתות הכוננות המקומיות נפלו בקרב. בבוקר זה החלה מלחמה.

בלילה ההוא לקח על עצמו אנדריי משימת אבטחה משטרתית – אבטחת מסיבת הטבע "נובה" ליד קיבוץ רעים שבצפון-מערב הנגב. עם תחילת מתקפת הטילים והגעת המחבלים למתחם המסיבה נרתם אנדריי עם שוטרים נוספים לחילוצם של אזרחים רבים שנכחו במסיבה. בתוך כך לחם בגבורה ובחירוף נפש בעזרת נשקו האישי כדי לסייע לאזרחים לעזוב את המקום והיה השוטר האחרון שנותר להילחם במתחם. במהלך הקרב נורה על ידי מחבלים ונהרג.

מפקח אנדריי פושיבאי נפל בקרב ביום כ"ב בתשרי תשפ"ד (7.10.2023). בן שלושים ותשע בנופלו. הובא למנוחות בבית העלמין הצבאי בבאר שבע. הותיר הורים, אח ואחות.

לאחר נפילתו הועלה לדרגת פקד.

בטקס סיום תואר מוסמך תוכנית פו"ם באוניברסיטת חיפה, בדצמבר 2024, קיבלה אחותו טטיאנה את התעודה שלו. במעמד זה לבשו חבריו ללימודים חולצות עם הדפס תמונתו.

באתר האינטרנט 7/10 Remember הועלה דף לזכרו, וסיפורו הועלה באתר עמותת חיל הטכנולוגיה והאחזקה. סרטון קצר שהופק בתום קורס קציני המשטרה ובו סיפר את סיפורו ניתן לצפייה באתר "יוטיוב" תחת הכותרת "לזכרו של אנדריי פושיבאי ז"ל".

אנדריי מונצח באנדרטת נרצחי מסיבת "נובה" בחניון יער רעים, באתר ההנצחה לחללי משטרת ישראל במכללת המשטרה בבית שמש ובאתר ההנצחה המשטרתי באינטרנט.